#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void _GetBottomLeftValue(TreeNode* root, int& ret, int depth, int& maxdapth)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            if (depth > maxdapth)
            {
                ret = root->val;
                maxdapth = depth;
            }
            return;
        }
        if (root->left)
            _GetBottomLeftValue(root->left, ret, depth + 1, maxdapth);
        if (root->right)
            _GetBottomLeftValue(root->right, ret, depth + 1, maxdapth);
    }
    int findBottomLeftValue(TreeNode* root) {
        int ret = root->val;
        int maxdapth = 0;
        _GetBottomLeftValue(root, ret, 0, maxdapth);
        return ret;
    }
};

class Solution {
public:
    bool _hasPathSumR(TreeNode* root, int& targetSum, int sum)
    {
        if (root == nullptr)
            return false;
        if (root->left == nullptr && root->right == nullptr && targetSum == sum + root->val)
        {
            return true;
        }
        return _hasPathSumR(root->left, targetSum, sum + root->val) || _hasPathSumR(root->right, targetSum, sum + root->val);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return _hasPathSumR(root, targetSum, 0);
    }
};

class Solution {
public:
    TreeNode* GetTree(vector<int>& inorder, vector<int>& postorder, int& rooti, int left, int right)
    {
        if (left > right)
            return nullptr;

        int mid = 0;
        TreeNode* cur = new TreeNode(postorder[rooti]);
        for (mid = inorder.size() - 1; mid >= 0; mid--)
        {
            if (inorder[mid] == postorder[rooti])
                break;
        }
        rooti--;
        cur->right = GetTree(inorder, postorder, rooti, mid + 1, right);
        cur->left = GetTree(inorder, postorder, rooti, left, mid - 1);

        return cur;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int rooti = inorder.size() - 1;
        return GetTree(inorder, postorder, rooti, 0, (postorder.size() - 1));
    }
};

